package cn.chen.算法.查找;

import java.util.Arrays;

/**
 * 斐波那契查找
 */
public class FibonacciSearch {

    public static int maxSize=20;
    public static void main(String[] args){

        int [] arr={1,5,9,456,1258,9654,12536};

        System.out.println("arr["+fibonacciSearch(arr,1)+"]");

        System.out.println(Arrays.toString(getFibonacci()));
    }
    // 获取斐波那契数列的方法
    public static int[] getFibonacci(){

        int [] fib=new int[maxSize];
        fib[0]=1;
        fib[1]=1;
        for(int i=2;i<maxSize;i++)
            fib[i]=fib[i-1]+fib[i-2];

        return fib;
    }
    // 斐波那契算法
    public static int fibonacciSearch(int[] arr,int value){

        int start=0,end=arr.length-1;
        int k=0;        // 用于表示斐波那契分割数值的下标
        int mid=0;  // 用于存放mid的值
        int f[]=getFibonacci();

        // [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
        while (end>f[k]-1)  // 获取斐波那契分割数值的下标 6<8-1 k=5
            k++;

        // 因为f[k]的值可能大于数组arr的长度，因此我们需要构造一个新数组并且指向arr，不足的部分用0补齐
        int[] temp= Arrays.copyOf(arr,f[k]);

        // 实际上需求使用arr数组最后的数填充temp
        for(int i=end+1;i<temp.length;i++){

            temp[i]=arr[end];
        }

        // 使用while来循环处理，找到我们的数value
        while(start<=end){  // 只要这个条件满足，就可以找

            mid=start+f[k-1]-1;     // 该公式就是找到斐波那契数列的分割点
            if(value<temp[mid]){    // 应该继续向数组的前面查找（左边）

                end=mid-1;

                // 为什么是k--？
                // 全部元素=前面元素+后面元素 f[k]=f[k-1]+f[k-2]
                // 因为前面有f[k-1]个元素，所以可以继续拆分成 f[k-1]=f[k-2]+f[k-3],即在f[k-1]前面继续查找k--，即下次循环mid=f[k-1-1]-1
                k--;
            }
            else if(value>temp[mid]) {  // 我们应该向后面查找（右边）

                start=mid+1;

                // 为什么是k -=2 ？？
                // 全部元素=前面元素+后边元素 f[k]=f[k-1]+f[k-2]
                // 因为后面还有f[k-2]个元素，所以可以继续拆分 f[k-1]=f[k-3]+f[k-4],即在f[k-2]的前面进行查找 k-=2 ,即下次循环mid=f[k-1-2]-1
                k-=2;
            }
            else {  // 找到了

                // 需要确定返回的是哪一个下标？
                if(mid<=end)
                    return mid;
                else
                    return end;

            }
        }
        return -1;
    }
}
